Deterministic Finite Automata
有限元自动机是一个对于有限内存的机器的很好的模拟
很多东西都是可以用状态机去表示的, 如一个开灯的开关, 如果在关灯状态, 则按开灯灯就打开, 按关灯按钮, 状态不变. 如果在开灯状态, 按关灯按钮会转跳到关灯状态, 按开灯按钮状态不变.
状态机通常会有一个特殊的状态是Accept状态, 如果最终指令执行完, 停在了这个状态, 则最终输出Accept, 否则输出reject.
并且, 状态机是可以被语言表示的, 比如我们可以设计出一种状态机, 它只会接受以下这种语言
每种状态机只会认识一种语言, 我们记作L(M) 如果这个状态机不接受任何字符串, 则这个L(M)是个空集.
我们可以把这个L(M)完全当作一个Language, 所以可以说
反过来, 如果一个语言可以被状态机所recognized, 则这个语言可以说是regular language
如:
不是个regular language, 之后会证明它为什么不是
需要注意的是, 每个状态机只会识别一个Language, 如果一个状态机识别集合A, 但有个集合B, 它是A的子集, 我们仍然不能说状态机识别B, 只能说它接受B. 因为如果需要识别, 则这个集合需要包含这个机器M所接受的所有字符串
对于有限元自动机, 他的功能就是去解决关于regular language的问题, 但限制就是无法解决关于不是regular language的问题.
k-tuple - a sequence of k elements, k≥1
对于一个有限元自动机M, 它有五个元组:
| 符号 | 意思 |
|---|---|
| a finite set of states, 有限的状态, 这里有三个 | |
| a finites set of symbols, called the alphabet, 这个自动机接受的符号 | |
| transition function, 转移方程 | |
| the start state, 只能有一个起始点, 这里是q1作为起始点 | |
| set of accept states, 能有多个结束的点 |
如果一个状态机的F是空集, 那么它是没有终点, 也就是说它不会接受任何字符串, 所以它识别的语言也是空集
设计状态机的过程就像算法一样, 没有固定的公式, 更多的是靠自己的感觉
比如
需要注意的是, 虽然上面说过如何让语言变成空集, 但我们仍然需要让状态机加上状态转移方程(也就是箭头), 不然这个状态机就没有任何alphabet. 除非题目明确规定alphabet也是空, 并且, alphabet里有的元素, 必须在每个状态机上都有箭头来应对新出现的字符
如果一个状态机添加了一个新的元素在alphabet中, 如果他的language没有改变, 则可以说这个状态机也没有改变, 就像在一个算法中添加了一条注释一样, 这个算法没有受到影响, 那么它就是本来的算法.
这是一种对于language的操作:
Union:
Star:
前面两个都比较好理解, 最后一个就是把A合集里任意多的元素以任意顺序和任意数量组合而成.
比如{0011},{},{0100111}都是{0,1}^*
并且, Concatenation也是有点注意的地方的: 如果合集B是个空集, 则A◦B也会是空集, 因为无法从B中选择任何元素, 所以也组成不了任何东西
这种操作也遵循闭包性质, 就像int+int永远会等于int的一样, 但int / int不一定会得到int一样
Proof:
Union
假设存在M1,M2两个机器, 分别认识两个语言A,B, 我们需要证明, 存在一个机器, 它认识A U B, 换句话说, 给一个String, 这个新机器M只有在M1或M2接受它的时候才会接受.
其实, 想找到这个新机器M, 是蛮容易的: 可以把M1和M2里所有的节点都组合起来, 成为一个一个的节点对. 然后把M1和M2所有的转移方程搬到M机器里面, 就可以得到一个新机器, 只接受M1或M2的String